package com.yequan.datastructure.algorithm.search;

/**
 * @author yequan
 * @date 2019/12/12
 */
public class BinarySearch {

    /**
     * 二分查找:只适用无重复有序数组
     *
     * @param array 有序数组
     * @param size  有序数组长度
     * @param value 要查找的数据
     * @return
     */
    public static int binarySearch(int[] array, int size, int value) {
        int low = 0;
        int high = size - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] == value) {
                return mid;
            } else if (array[mid] < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 递归方式实现二分查找
     *
     * @param array 有序数组
     * @param size  有序数组长度
     * @param value 要查找的数据
     * @return
     */
    public static int binarySearchInternally(int[] array, int size, int value) {
        return binarySearchInternallyHandler(array, 0, size - 1, value);
    }

    /**
     * 递归调用
     *
     * @param array
     * @param low
     * @param high
     * @param value
     * @return
     */
    private static int binarySearchInternallyHandler(int[] array, int low, int high, int value) {
        if (low > high) {
            return -1;
        }
        int mid = low + ((high - low) >> 1);
        if (array[mid] == value) {
            return mid;
        } else if (array[mid] < value) {
            return binarySearchInternallyHandler(array, mid + 1, high, value);
        } else {
            return binarySearchInternallyHandler(array, low, mid - 1, value);
        }
    }

    /**
     * 查找第一个值等于给定值的元素
     *
     * @param array
     * @param size
     * @param value
     * @return
     */
    public static int binarySearchMutation1(int[] array, int size, int value) {
        int low = 0;
        int high = size - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] < value) {
                low = mid + 1;
            } else if (array[mid] > value) {
                high = mid - 1;
            } else {
                if (mid == 0 || array[mid - 1] != value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 查找最后一个值等于给定值的元素
     *
     * @param array
     * @param size
     * @param value
     * @return
     */
    public static int binarySearchMutation2(int[] array, int size, int value) {
        int low = 0;
        int high = size - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] < value) {
                low = mid + 1;
            } else if (array[mid] > value) {
                high = mid - 1;
            } else {
                if (mid == size - 1 || array[mid + 1] != value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    /**
     * 查找第一个大于等于给定值的元素
     *
     * @param array
     * @param size
     * @param value
     * @return
     */
    public static int binarySearchMutation3(int[] array, int size, int value) {
        int low = 0;
        int high = size - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == 0 || array[mid - 1] < value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 查找最后一个小于等于给定值的元素
     *
     * @param array
     * @param size
     * @param value
     * @return
     */
    public static int binarySearchMutation4(int[] array, int size, int value) {
        int low = 0;
        int high = size - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else {
                if (mid == size - 1 || array[mid + 1] > value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    /**
     * 用于比对的遍历查找
     *
     * @param array
     * @param value
     * @return
     */
    public static int search(int[] array, int value) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == value) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = new int[100000000];
        for (int i = 1; i <= 100000000; i++) {
            array[i - 1] = i;
        }
        long bStart = System.nanoTime();
        int index2 = binarySearchInternally(array, 100000000, 854203062);
        long bEnd = System.nanoTime();
        System.out.println("二分查找: 854203062的位置: " + index2 + "  耗时: " + (bEnd - bStart));
        long cStart = System.nanoTime();
        int index3 = search(array, 854203062);
        long cEnd = System.nanoTime();
        System.out.println("普通遍历查找: 854203062的位置: " + index3 + "  耗时: " + (cEnd - cStart));

        int[] array1 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 12, 13, 15, 15, 15, 23, 23, 23, 24, 24, 24, 24, 24, 24, 45};
        int index4 = binarySearchMutation1(array1, array1.length, 23);
        System.out.println("第一个23位置: " + index4);

        int index5 = binarySearchMutation2(array1, array1.length, 23);
        System.out.println("最后一个23的位置: " + index5);

        int index6 = binarySearchMutation3(array1, array1.length, 14);
        System.out.println("第一个大于等于14的位置: " + index6);

        int index7 = binarySearchMutation4(array1, array1.length, 14);
        System.out.println("最后一个小于等于14的位置: " + index7);
    }

}
